package shuati.shua;

/**
 * @author ldltd
 * @create 2025-05-16-19:48
 * @describe 二分查找
 */
public class BinarySearch {
    /*
    一、基本框架与边界选择
          1. 搜索区间定义
        二分查找的核心在于明确你的"搜索区间"是什么：
        [0, length-1]：这是最常见的，当你确定元素一定在数组范围内时使用
        [0, length]：当可能需要返回一个"超出数组边界"的位置时（如插入位置）
        [-1, length-1]：特殊情况下使用，较少见

        2. 循环条件选择
        while (left <= right)：
            搜索区间是闭区间 [left, right]
            退出条件是 left > right（即 left = right + 1）
            适用于精确查找
        while (left < right)：
            搜索区间是左闭右开 [left, right)
            退出条件是 left == right
            适用于寻找边界或插入位置
    二、经验口诀
        1.区间选择口诀：
            "有界闭区间，0到len-1"
            "无界开区间，0到len"
        2.循环条件口诀：
            "精确查找用<=，边界查找用<"
            "<=要变mid±1，<只变一边值"
        3.更新规则口诀：
            "找到目标不一定停，看你要找啥"
            "左移right=mid-1，右移left=mid+1"
            "边界查找保留mid，缩小范围慢慢来"
    三、常见模式与示例
        模式1：精确查找（元素是否存在）
    * */
    int binarySearch(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return -1; // 未找到
    }
        /*
        * 特点：
            使用 <= 循环条件
            找到立即返回
            未找到返回-1
            模式2：寻找左边界
        * */
        int leftBound(int[] nums, int target) {
            int left = 0, right = nums.length; // 注意right初始值
            while (left < right) {
                int mid = left + (right - left) / 2;
                if (nums[mid] >= target) {
                    right = mid;
                } else {
                    left = mid + 1;
                }
            }
            return left; // 返回的是插入位置
        }
        /*
            特点：
            使用 < 循环条件
            right初始为length
            相等时移动right不移动left
            模式3：寻找右边界
        * */
        int rightBound(int[] nums, int target) {
            int left = 0, right = nums.length;
            while (left < right) {
                int mid = left + (right - left) / 2;
                if (nums[mid] <= target) {
                    left = mid + 1;
                } else {
                    right = mid;
                }
            }
            return left - 1; // 返回的是最后一个等于target的位置
        }
        /*
            特点：
            使用 < 循环条件
            相等时移动left不移动right
            最后返回left-1
        四、变更条件总结表
            情况	    循环条件	left更新	right更新	初始right	适用场景
            精确查找	<=	    mid+1	mid-1	    len-1	    查找元素是否存在
            左边界	<	    mid+1	mid	        len	        找第一个>=target
            右边界	<	    mid+1	mid	        len	        找最后一个<=target
            插入位置	<	    mid+1	mid	        len	        找元素应插入位置
        五、实战示例分析
            问题：在有序数组 [1,2,2,2,3] 中查找 2 的起始和结束位置
            1.找左边界：
                初始: left=0, right=5
                第一次mid=2 (nums[2]=2) → right=2
                第二次mid=1 (nums[1]=2) → right=1
                第三次mid=0 (nums[0]=1) → left=1
            退出循环，left=1
            2.找右边界：
                初始: left=0, right=5
                第一次mid=2 (nums[2]=2) → left=3
                第二次mid=4 (nums[4]=3) → right=4
                第三次mid=3 (nums[3]=2) → left=4
                退出循环，left=4 → 返回left-1=3
            最终结果：[1,3]
           **/
        public static void main(String[] args) {
            int [] ar=new int[]{1,2,2,2,3};
            int l1=0,r1=ar.length;
            int mid1;
            //二分查找左边界
            while (l1<r1){
                mid1=l1+(r1-l1)/2;
                System.out.println("l1="+l1+" r1="+r1+" mid1="+mid1);
                if (ar[mid1]<2){
                    l1=mid1+1;
                }else {
                    r1=mid1;
                }

            }
            //二分查找右边界
            int l2=0,r=ar.length;
            int mid2;
            while (l2<r){
                mid2=l2+(r-l2)/2;
                System.out.println("l2="+l2+" r="+r+" mid2="+mid2);
                if (ar[mid2]<=2){
                    l2=mid2+1;
                }else {
                    r=mid2;
                }
            }
            //输出结果[l1,l2-1]
            System.out.println("l1="+l1+" l2="+l2);
        }
    /*/
        六、常见错误与修正
            1.死循环：
                原因：left和right更新不当，如left=mid导致无法缩小范围
                修正：确保每次迭代范围都在缩小
            2.漏掉元素：
                原因：使用<时漏掉left==right的情况
                修正：根据需求选择合适的循环条件
            3.数组越界：
                原因：right初始为length-1但使用了length的逻辑
                修正：统一初始值和循环条件
        * */
}
